//
// Created by ade on 2022/9/15.
//

#include <iostream>
#include <vector>

using namespace std;

// 思路：找到一个标杆，标杆左侧有大于标杆的值记录index，标杆右侧有小于标杆的值记录index，交换两个找到的index.
// 保证标杆左侧都是小于等于的，标杆右侧都是大于等于的
void quick_sort(vector<int> &nums, int l, int r) {
    if (l > r) return;
    int tmp = nums[l];
    int start = l, end = r;
    while (l < r) {
        while (nums[l] < tmp && l < r) l++;
        while (nums[r] >= tmp && l < r) r--;
        swap(nums[l], nums[r]);
    }
    if (nums[l] >= nums[end])
        swap(nums[l], nums[end]);
    else
        l++;
    quick_sort(nums, start, l - 1);
    quick_sort(nums, l + 1, end);
}

int main() {
    vector<int> nums = {3, 6, 8, 9, 1, 2, 10, 11, 4, 5, -1, -1};
    quick_sort(nums, 0, nums.size() - 1);
    for (auto i : nums) {
        cout << i << ",";
    }
    return 0;
}